#include <iostream>
using namespace std;



typedef struct {
    int** sum;
    int R;
} NumMatrix;

NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
    obj->sum = (int**)malloc(sizeof(int*) * (matrixSize + 1));
    int i = 0;
    for (i = 0; i < matrixSize + 1; i++)
    {
        obj->sum[i] = (int*)calloc((*matrixColSize) + 1, sizeof(int));
    }
    int j = 0;
    for (i = 0; i < matrixSize; i++)
    {
        for (j = 0; j < *matrixColSize; j++)
        {
            obj->sum[i + 1][j + 1] = obj->sum[i + 1][j] + obj->sum[i][j+1] - obj->sum[i][j] + matrix[i][j];
        }
    }
    obj->R = matrixSize + 1;
    return obj;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    return obj->sum[row2 + 1][col2 + 1] - obj->sum[row2+1][col1] - obj->sum[row1][col2+1] + obj->sum[row1][col1];
}

//[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]
int main()
{
    int a1[] = { 3,0,1,4,2 };
    int a2[] = { 5,6,3,2,1 };
    int a3[] = { 1,2,0,1,5 };
    int a4[] = { 4,1,0,1,7 };
    int a5[] = { 1,0,3,0,5 };
    int* Array[] = {a1,a2,a3,a4,a5};
    int r = 5;
    int c = 5;
    NumMatrix* obj = numMatrixCreate(Array,r,&c);

    int ret = numMatrixSumRegion(obj,1,2,2,4);
    cout << ret << endl;
	return 0;
}